package pers.vic.basics.leetcode;

import com.sun.org.apache.bcel.internal.generic.RETURN;
import jdk.internal.dynalink.beans.StaticClass;

import java.sql.CallableStatement;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Stream;

/**
 * @author Vic.xu
 * @description: 43. 字符串相乘 {@literal https://leetcode-cn.com/problems/multiply-strings/}
 * @date: 2020/12/4 0004 16:25
 */
public class J0043_M_Multiply {

    /*
    给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
    说明：
    num1 和 num2 的长度小于110。
    num1 和 num2 只包含数字 0-9。
    num1 和 num2 均不以零开头，除非是数字 0 本身。
    不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。
     */

    /**
     * 是时候证明我是读过小学的人了 ， 手写竖式相乘吧
     * 1 2 3
     * 1 5 6
     * ---------
     * 7 3 8
     * 6 1 5 0
     * 1 2 3 0 0
     * -----------
     * 1 9 1 8 8
     */
    public static String multiply(String num1, String num2) {
        // 先把字符串反转一下  方便从地位开始相乘, 虽然浪费了点空间  但是理解起来方便一点
        char[] cs1 = new StringBuilder(num1).reverse().toString().toCharArray();
        char[] cs2 = new StringBuilder(num2).reverse().toString().toCharArray();
        // 存放每cs2每一位和 cs1相乘的结果集的
        List<List<Integer>> list = new ArrayList<>();
        //进位
        int carry = 0;
        for (int i = 0; i < cs1.length; i++) {
            List<Integer> temp = new ArrayList<>();
            //补0
            for (int k = 0; k < i; k++) {
                temp.add(0);
            }
            int c1 = cs1[i] - '0';
            carry = 0;
            for (int j = 0; j < cs2.length; j++) {
                int c2 = cs2[j] - '0';
                int product = c1 * c2 + carry;
                temp.add(product % 10);
                carry = product / 10;
            }
            //不管进位是多少 都记录下来
            temp.add(carry);
            list.add(temp);
        }
        /*
         *      7 3 8
         *    6 1 5 0
         *  1 2 3 0 0
         */
        // 累加每一位
        StringBuilder sb = new StringBuilder();
        int max = list.get(list.size() - 1).size();
        carry = 0;
        for (int i = 0; i < max; i++) {
            int num = 0;
            for (List<Integer> temp : list) {
                if (temp.size() > i) {
                    num += temp.get(i);
                }
            }
            num += carry;
            sb.append(num % 10);
            carry = num / 10;
        }
        if (carry != 0) {
            sb.append(carry);
        }
        sb = sb.reverse();
        return removeBeginZero(sb);
    }

    private static String removeBeginZero(StringBuilder sb){
        if (sb.length() == 0) {
            return "0";
        }
        if (sb.charAt(0) == '0') {
            return removeBeginZero(sb.deleteCharAt(0));
        }
        return sb.toString();
    }


    public static void main(String[] args) {

        System.out.println(789 * 123);
        List<Integer> a = new ArrayList<>();
        System.out.println(multiply("789", "123"));
    }
}
